package shu.segment;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Trie {


    private final Node root;
    private int size;
    public Trie() {
        this.root = new Node();
        this.size = 0;
    }

    public static void main(String[] args) {
        String[] strs = {"dog", "panda", "service", "ex_serviceman", "gun", "army", "oil", "coal", "petol", "pan"};
        Trie trie = new Trie();
        Arrays.stream(strs).forEach(item -> trie.addStr(item));
        System.out.println(trie.getSize());
        System.out.println(trie.matchWord("pandog"));

        System.out.println(trie.search("p."));
    }

    public int getSize() {
        return this.size;
    }

    // 添加操作
    public void addStr(String str) {
//判断，定义辅助节点，循环，定义map，判断比较keyset，put添加，循环条件，判断单词是否为true（是，则size++）
        if (str.length() == 0 || str == null) {
            return;
        }
        Node cur = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.containsKey(c)) {
                children.put(c, new Node());
            }
            cur = children.get(c);
            if (!cur.isWord) {
                cur.isWord = true;
                size++;
            }
        }

    }

    // 判断是否存在指定的单词
    public boolean matchWord(String word) {
        if (word.length() == 0 || word == null) {
            return false;
        }
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.containsKey(c)) {
                return false;
            }
            cur = children.get(c);
        }
        return cur.isWord;
    }

    // 判断是否存在以pre开始的单词
    public boolean matchStartPre(String pre) {
        if (pre.length() == 0 || pre == null) {
            return false;
        }
        Node cur = root;
        for (int i = 0; i < pre.length(); i++) {
            char c = pre.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.containsKey(c)) {
                return false;
            }
            cur = children.get(c);
        }
        return true;
    }

    public boolean search(String express) {
        if (express == null && express.length() == 0) {
            return false;
        }
        return match(root, express, 0);
    }


    /**
     * @param node    当前结点
     * @param express 表达式
     * @param index   表达式中匹配字符的索引
     * @return
     */
    private boolean match(Node node, String express, int index) {
//判断index，截取字符串，判断c等不等于.,等于执行上面那一套，后加递归条件，不等于遍历
        if (index == express.length()) {
            return true;
        }
        char c = express.charAt(index);
        if (c != '.') {
            Map<Character, Node> children = node.next;
            if (!children.containsKey(c)) {
                return false;
            }
            return match(children.get(c), express, index + 1);
        } else {
            Map<Character, Node> children = node.next;
            Set<Character> set = children.keySet();
            for (Character str : set) {
                if (match(children.get(str), express, index + 1)) {
                    return true;
                }
            }
            return false;
        }

    }

    @Override
    public String toString() {
        return "Trie{" +
                "root=" + root +
                ", size=" + size +
                '}';
    }

    /*
     * 处理字符串
     * */
    private class Node {
        boolean isWord;
        Map<Character, Node> next;

        Node() {
            isWord = false;
            next = new HashMap<>();
        }
    }
}
